Databases may be implemented according to a variety of different database models, such as relational, non-relational, graph, columnar (also known as extensible record; e.g., HBase), object, tabular, tuple store, and multi-model. Examples of non-relational database models (which are also referred to as schema-less and NoSQL) include key-value store and document store (also known as document-oriented as they store document-oriented information, which is also known as semi-structured data). A database may comprise one or more database objects that are managed by a Database Management System (DBMS), each database object may include a number of records, and each record may comprise of a set of fields. A record may take different forms based on the database model being used and/or the specific database object to which it belongs; for example, a record may be: 1) a row in a table of a relational database; 2) a JavaScript Object Notation (JSON) document; 3) an Extensible Markup Language (XML) document; 4) a key-value pair; etc. A database object can be unstructured or have a structure defined by the DBMS (a standard database object) and/or defined by a user (custom database object). In some implementations of a cloud database (a database that runs on a cloud platform and that is provided as a database service), identifiers are used instead of database keys, and relationships are used instead of foreign keys.
A database may contain thousands or even millions of records. To process so many records efficiently, one may split the database records into more manageable chunks (also referred to as pages). Each of these chunks/pages may be processed by one thread within a multi-thread computing environment. The splitting process may be referred to as pagination. To paginate, one may issue queries to the database (sometimes referred to as paged queries), and each query returns a page from the database records.
One approach is to use offset with limit (also referred to as OFFSET with LIMIT or limit, LIMIT OFFSET) based queries to split a table of records into similarly sized subsets of records. For example, a query may cause the retrieval of 50 records starting from offset 100 by using the offset with limit based query LIMIT 50 OFFSET 100. A series of offset with limit based queries that specify the same limit (e.g., 50) and different offsets (e.g., 50, 100, 150, 200, 250, etc.) may split the table into similarly sized subsets of records. The advantage of such queries is that no knowledge of the values in the fields of the records is required, but rather one may generate the series of queries based on just the total number of records and the limit (also referred to as the targeted page number). For example, if 3,000 records are to be split into two pages (e.g., so that each page of records is to be executed by a thread), two offset with limit based queries may be issued: (1) LIMIT 1,500 OFFSET 0; and (2) LIMIT 1,500 OFFSET 1,500. One may specify these two queries without knowing any values in the fields of the records.
Yet the offset with limit based queries may be computationally inefficient, especially when operating on a relatively large number of records and/or being used to generate a relatively large number of subsets. The offset with limit based queries must use increasing values for the offsets. Thus, a database management system (DBMS) must read and skip each record from the beginning (record 0) until it reaches the offset value specified in a query. For example, an offset with limit based query of LIMIT 50 OFFSET 10,000 means that 9,999 records are read and skipped before reaching the starting point of a page for the query. The DBMS needs to keep counting the records, and the operations take memory space and consume computing (e.g., central processing unit (CPU)/graphics processing unit (GPU)) time. For example, when there are one million records to paginate and one of 10 threads to process each page, the last two threads will respectively use queries with the values 800,000 and 900,000 for the offset, means that they will respectively read and skip 799,999 and 899,999 records. Computers may not have enough memory space and/or computing resources to implement such offset with limit based queries for pagination of a large number of records. Indeed, experiments show that using the offset with limit based queries to paginate around ten million records may result in a time out. Thus, the offset with limit based queries is inefficient for pagination of a large number of records.